package warm100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class findAnagrams_438 {
    public List<Integer> findAnagrams(String s, String p) {
        //利用滑动窗口，窗口遍历到非p中字母，窗口直接右滑到该字母右边一位
        //需要保证任意时刻窗口内无其他元素
        char[] chars = s.toCharArray();
        char[] ps = p.toCharArray();
        List<Integer> ans = new ArrayList<>();
        if(p.length()==1){
            for (int i = 0; i < chars.length; i++)
                if(chars[i]==ps[0])ans.add(i);
            return ans;
        }
        HashSet<Character> set = new HashSet<>();
        for (char c : ps)
            set.add(c);
        int l = 0, r = -1, size = p.length();  //窗口左右边界
        for (int i = 0; i < chars.length; i++) {
            if(l > chars.length-p.length())
                break;
            if (set.contains(chars[i])) {      //符合条件的
                r++;           //窗口右移
                if (r - l + 1 == size){         //窗口大小足够
                    if (isAnagram(chars, l, ps))
                        ans.add(l);
                     l++;
                }
            } else {                 //不符合条件的字母
                l=i+1;
                r=i+1;
            }
        }
        return ans;
    }

    /**
     * 是否是p的异位词
     *
     * @param start 起始位置
     * @param p
     * @return
     */
    boolean isAnagram(char[] chars, int start, char[] p) {
        int[] s = new int[26];
        for (char c : p)
            s[c - 'a']++;
        for (int i = start; i < start + p.length; i++)
            s[chars[i] - 'a']--;
        for (int i = 0; i < 26; i++)
            if (s[i] != 0) return false;
        return true;
    }


    /**
     * 不定长滑动窗口
     */
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] cnt = new int[26]; // 统计 p 的每种字母的出现次数
        for (char c : p.toCharArray()) {
            cnt[c - 'a']++;
        }
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            int c = s.charAt(right) - 'a';
            cnt[c]--; // s中右端点字母c进入窗口，与p中字母c匹配
            //如果字母c不存在于p中，left会一直将前面的字母全部跳过，直到跳过e
            while (cnt[c] < 0) { // 当前字符串，字母 c 个数比p中c多，不符合要求，窗口滑动
                cnt[s.charAt(left) - 'a']++;  // 左端点字母离开窗口，需要恢复p中对应字母的个数，便于之后继续匹配
                left++;
            }
            //内层循环结束后，s的每种字母的出现次数，都小于等于 p 的每种字母的出现次数。
            // 如果 s的其中一种字母的出现次数比 p 的小，那么 s的长度必然小于 p 的长度。
            // 所以只要 s的长度等于 p 的长度，就说明 s的每种字母的出现次数，和 p 的每种字母的出现次数都相同
            if (right - left + 1 == p.length()) { // s' 和 p 的每种字母的出现次数都相同
                ans.add(left); // s' 左端点下标加入答案
            }
        }
        return ans;
    }
}
